今天的題目為100.Same Tree,而這一題是在叫我們寫出:
給定兩棵二元樹的根節點 p 和 q,寫一個函式來判斷這兩棵樹是否相同
兩棵二元樹被視為相同,需同時滿足以下條件:
結構完全一致(每個節點的位置與左右子樹的配置相同)、對應的節點值完全相同
以下是這題的程式碼:
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q == null){
return true;
}
if(p == null || q == null){
return false;
}
if(p.val != q.val){
return false;
}
return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}
}
以下是解說:
這段程式碼是在定義一個Solution的類別,裡面有一個方法叫 isSameTree,功能是判斷兩棵二元樹是不是一模一樣,這個方法會接收兩個參數p和q,它們是兩棵樹的根節點。
一開始進來的時候,程式會先看p和q是不是都等於 null,如果是的話,代表這個位置兩棵樹都沒東西,那就算是相同,直接回傳true。
再來它會判斷是不是只有其中一個是 null,如果是的話就代表一棵樹有節點、另一棵沒有,結構就不一樣了,回傳 false。
然後它會比對兩個節點的值是不是一樣,如果不一樣,那也不能算是相同的樹,回傳 false。
最後一行很重要,它會用遞迴的方式去比較左右子樹是不是也一樣,只要左邊跟右邊的子樹都一樣,整棵樹才算是相同的,所以它用 [&&] 把左右子樹的結果合起來。
整體來說,這是一個遞迴解法,從根節點開始一路往下比對每個節點和它的左右子樹,直到整棵樹都比完。這種方式很適合用來處理樹狀結構的問題,簡單又直覺。